//
// Created by madison on 2022/7/26.
//

#include "vector"

using namespace std;

class Solution {
public:
    // 方法一：暴力法
    int maxProfit(vector<int> &prices) {
        int n = prices.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                ans = max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }

    // 方法二：一次遍历 (双指针解决)
    int maxProfit1(vector<int> &prices) {
        int inf = 1e9;
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

int main() {
    Solution solution;
    vector<int> prices = {7, 1, 5, 3, 6, 4};
    printf("%d", solution.maxProfit1(prices));
    return 0;
}